\begin{frame}
\frametitle{Deterministic tiling systems}

\begin{define}[tl2br-deterministic tiling system \cite{LonatiPradella2011}]
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is tl2br-deterministic if for
any $\gamma_1, \gamma_2, \gamma_3, \gamma_4\in\Gamma\cup\{\#\}$ and $\sigma\in
\Sigma$ there exists at most one tile $t\in \Theta$ with \(t = \begin{smallmatrix}
\gamma_1& \gamma_2\\
\gamma_3& \gamma_4
\end{smallmatrix}
\), and $\pi(\gamma_4) = \sigma$.
\end{define}

$L \in REC$ is a deterministic picture language if and only if it admits a
deterministic tiling system for some $d \in c2c$(Corner to Corner).

The family of all deterministic REC picture languages is denoted by DREC.

\end{frame}

\begin{frame}

\frametitle{Example}
An example for a tiling system that is $tl2br$-deterministic we can cite the
language $L_{fr=fc}$ with the tiling system of
example\ref{unambiguousTilingSystemExample}. 
Remark that it is not $br2tl$-deterministic: tiles 
\setlength{\tabcolsep}{3pt}
\begin{tabular}{|c|c|}
\hline
 $a_{a}^1$ & $a_{a}^2$\\
\hline
 $a_{a}^0$ & $b_{a}^1$\\
\hline
\end{tabular}, 
\begin{tabular}{|c|c|}
\hline
 $a_{b}^1$ & $a_{a}^2$\\
\hline
 $a_{a}^0$ & $b_{a}^1$\\
\hline
\end{tabular}
\setlength{\tabcolsep}{6pt} $\in\Theta$ with $\pi(a_{a}^1) = \pi(a_{b}^1) = a$.

\parskip 30pt

Another kind of determinism for tiles, introduced in
\cite{Lonati:2009:STS:1616390.1616439}, is to build a picture $p \in
\Sigma^{**}$ by scanning $p$ with a polite strategy\cite{ITA:8215469}.
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{polite scanning strategy}
\begin{define}[\cite{LonatiPradella2011}]
A polite scanning strategy is a tripel $\mu = (\eta, c_s, d_s)$, where
\begin{itemize}
  \item $\eta: 2^{Dirs}\times Dirs \rightarrow Dirs$ is a partial function such
  that $\eta(D, d) = \perp$ if $-d\not\in D$
  \item $c_s$ is the starting corner
  \item $d_s$ is the starting direction
\end{itemize}
\end{define}

In \cite{ITA:8215469} it was proved that any polite scanning strategy
has to follow, except for some bootstrap steps, one of four kinds of movements,
or their rotations and symmetrical, intuitively exemplified by the following
pictures.

\captionsetup[table]{labelformat=empty}
\footnotesize  
\setlength{\tabcolsep}{4pt}

\begin{minipage}[b]{0.2\linewidth}
\begin{table}
\begin{tabular}{|D{0.3cm}|D{0.3cm}|D{0.3cm}|D{0.3cm}|}
\hline
1&6&7&12\tabularnewline
\hline
2&5&8&11\tabularnewline
\hline
3&4&9&10\tabularnewline
\hline
\end{tabular}
\caption{(a) snake($\mathcal{S}$)}
\end{table}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{table}
\begin{tabular}{|D{0.3cm}|D{0.3cm}|D{0.3cm}|D{0.3cm}|}
\hline
 1&10&11&12\tabularnewline
\hline
 2&9&8&7\tabularnewline
\hline
 3&4&5&6\tabularnewline
\hline
\end{tabular}
\caption{(b) L-like($\mathcal{J}$)}
\end{table}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{table}
\begin{tabular}{|D{0.3cm}|D{0.3cm}|D{0.3cm}|D{0.3cm}|}
\hline
 1&12&9&8\tabularnewline
\hline
 2&11&10&7\tabularnewline
\hline
 3&4&5&6\tabularnewline
\hline
\end{tabular}
\caption{(c) U-like($\mathcal{U}$)}
\end{table}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{table}
\begin{tabular}{|D{0.3cm}|D{0.3cm}|D{0.3cm}|D{0.3cm}|}
\hline
 1&10&9&8\tabularnewline
\hline
 2&11&12&7\tabularnewline
\hline
 3&4&5&6\tabularnewline
\hline
\end{tabular}
\caption{(d) spiral($\mathcal{C}$)}
\end{table}
\end{minipage}

\setlength{\tabcolsep}{6pt}
\normalsize

The directions of the here depicted versions are called left-to-right. In the
case of the snake-like strategy we denoted it by $\mathcal{S}^{l2r}$, while its
rotation is denoted by $\mathcal{S}^{t2b}$.

\end{frame}

\begin{frame}
\frametitle{$\mu$-deterministic tiling systems}

\begin{define}[$\mathcal{S}^{t2b}$-deterministic tiling system]
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is
$\mathcal{S}^{t2b}$-deterministic if $\Gamma$ and $\Theta$ can be partioned as
$\Gamma = \Gamma_1 \cup\Gamma_2, \Theta = \Theta_1\cup\Theta_2$, where 
\begin{itemize}
  \item $(\Sigma, \Gamma, \Theta_1,\pi)$ is $tl2br$-deterministic and for each
  tile $t\in\Theta_1, t(i, j)\in\Gamma_{3-i}\cup\{\#\}$
  \item $(\Sigma, \Gamma, \Theta_2,\pi)$ is $tr2bl$-deterministic and for each
  tile $t\in\Theta_2, t(i, j)\in\Gamma_{i}\cup\{\#\}$ and not both $t(1,1),
  t(1,2)$ are $\#$.
\end{itemize}
\end{define}
\end{frame}

\begin{frame}
\frametitle{Language hierarchy}
The closure under rotation of languages recognized by
$\mathcal{S}^{d}$-deterministic tiling systems, $d\in\{t2b, b2t, l2r, r2l\}$
is denoted by $\mathcal{S}$-DREC. Scan-DREC is the union of all such deterministic
classes that uses polite scanning strategies and Diag-DREC the union of all that
scans a given picture $c2c$ so that these corners are diagonal.

\begin{thm}
DREC $\subset$ Col-UREC $\cap$ Row-UREC\\
$\mathcal{S}$-DREC = Col-UREC $\cup$ Row-UREC, \\
the class Diag-DREC is equal to the closure by rotation of $\mathcal{L}(DOTA)$,
\\ Scan-DREC $\subset$ REC.
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Closure properties and decidable problem}

\begin{thm}
The family DREC is closed under complement but it is not closed under union
and intersection.
\end{thm}

\begin{thm}[\cite{AnselmoGiammarresiMadonia2007}]
It is decidable whether a given tiling system is d-deterministic for $d \in
c2c$.
\end{thm}

\begin{proof}
\setlength{\tabcolsep}{3pt} 
Given a tiling system $\mathcal{T} = (\Sigma, \Gamma, \Theta, \pi)$, in order to
test, for example, whether it is $tl2br$-deterministic it suffices to verify
whether there exist in $\Theta$ two tiles \begin{tabular}{|c|c|} 
\hline
 $\gamma_1$ & $\gamma_2$ \\
\hline 
 $\gamma_3$ & $\gamma_4$ \\
\hline
\end{tabular}, 
\begin{tabular}{|c|c|} 
\hline
 $\gamma_1$ & $\gamma_2$ \\
\hline 
 $\gamma_3$ & $\gamma_4'$ \\
\hline
\end{tabular} $\in\Theta$ ,with $\gamma_4 \neq \gamma_4'$ and
$\pi(\gamma_4) = \pi(\gamma_4')$.
\end{proof}
\setlength{\tabcolsep}{6pt} 

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Deterministic Process}
\setlength{\tabcolsep}{3pt} 
\begin{definition}[Deterministic Process~\cite{Reinhardt1998}]
Let $T = (\Sigma,\Gamma,\Theta,\pi)$ be a domino tiling system. Extend $\Theta$
to $\Theta' = \Theta\cup\{$\begin{tabular}{|c|} 
\hline
 s \\
\hline
 r \\
\hline
\end{tabular}, \begin{tabular}{|c|} 
\hline
 s \\
\hline
 f \\
\hline
\end{tabular}, \begin{tabular}{|c|} 
\hline
 g \\
\hline
 r \\
\hline
\end{tabular}, \begin{tabular}{|c|c|} 
\hline 
q & o \\
\hline 
\end{tabular}, \begin{tabular}{|c|c|} 
\hline 
q & d \\
\hline 
\end{tabular}, \begin{tabular}{|c|c|} 
\hline 
e & o \\
\hline 
\end{tabular}, $\mid$ \begin{tabular}{|c|} 
\hline
 g \\
\hline
 r \\
\hline
\end{tabular}, \begin{tabular}{|c|c|} 
\hline 
e & d \\
\hline 
\end{tabular} $\in\Theta$, $s = \pi(g), r = \pi(f), q = \pi(e), o = \pi(d)\}$
by also allowing the image symbols in the tiling.
\setlength{\tabcolsep}{6pt} 
 
For two intermediate configuations $p, p'\in
(\Sigma\cup\Gamma\cup\{\#\})^{m,n},$ $n,m \geq 1$ we allow a replacement step $p
\underset{(\Theta, \pi)}{\Rightarrow} p'$ if for all $i \leq m, j \leq n$ we
have either $p(i,j) = p'(i,j)$ or $p(i,j) = \pi(p'(i,j))$ and 
\end{definition}

\begin{definition}
\footnotesize
\begin{tabular}{|C{1.2cm}|} 
\hline
$p(i,j-1)$\tabularnewline
\hline
$p'(i,j)$\tabularnewline
\hline
\end{tabular}, \begin{tabular}{|C{1.2cm}|} 
\hline
 $p'(i,j)$ \tabularnewline
\hline
 $p(i,j+1)$ \tabularnewline
\hline
\end{tabular}, \begin{tabular}{|C{1.2cm}|C{1.2cm}|} 
\hline 
$p(i-1,j)$ & $p'(i,j)$ \tabularnewline
\hline 
\end{tabular}, \begin{tabular}{|C{1.2cm}|C{1.2cm}|} 
\hline  
$p'(i,j)$ & $p(i+1,j)$  \tabularnewline
\hline 
\end{tabular} 
\normalsize 
 $\in \Theta'$ and if the choice $p'(i,j)$ was 'forced', that means there is no
 other $g \neq p'(i,j)$ in $\Gamma$ with $p(i,j) = \pi(g)$ such that replacing
 $p(i,j)$ in $p$ by $g$ would result in each of the $4$ tiles containing this $g$ is in  $\Theta'$.
\end{definition}

The accepted language is $\mathcal{L}_d(\Theta,\pi) :=
\{p\in\Sigma^{*,*}\mid\hat{p} \overset{*}{\underset{(\Theta, \pi)}{\Rightarrow}}
p'\in(\Gamma\cup\{\#\})^{*,*}\}$. 

A picture language $L\subseteq\Sigma^{*,*}$ is
called determnistically recognizable if there are $\Theta, \pi$ with $L =
\mathcal{L}_d(\Theta,\pi)$.

\begin{thm}
$\mathcal{L}_d(\Theta,\pi)\subseteq\mathcal{L}(\Theta,\pi)$
\end{thm}

\end{frame}